The invention relates generally to management and synchronization of message traffic in a virtual time system, and deals more particularly with managing message sequence numbers during processing in a virtual time system. The invention is presented in the specific context of logic simulation performed on parallel processors operating on a virtual time basis.
In a "virtual time" system, multiple processors operate in parallel to perform specific processing tasks whose results are integrated into a system result. The individual processors of the system are synchronized by global virtual time (GVT). Jefferson defines GVT as the least of: all local virtual times, and the virtual send times of all unprocessed messages transmitted between the parallel processors. D. R. Jefferson, "Virtual Time", ACM Transactions on Programming Languages and Systems, pp. 404-425, July 1985.
An exemplary virtual time system comprising a plurality of processor nodes with means for calculating GVT is described in U.S. Pat. No. 5,250,943, commonly assigned herewith, and incorporated herein by reference.
Typically, any processor of a virtual time system may ask for calculation of GVT. In response to such a request, each processor reports to the requesting processor a minimum virtual time taken from the minimum of the LVT at the processor and the virtual time of any message that the processor has sent to another processor without yet having received an acknowledgment. Lin and Lazowska propounded an algorithm for determining GVT in a virtual time system comprising a message-passing, multi-processor environment. Y. Lin and E. D. Lazowska, "Determining the Global Virtual Time in a Distributed System", in Proceedings of the International Conference on Parallel Processing, pp. 201-209, 1990. In this algorithm, an initiator process broadcasts a START message causing every other process to compute its minimum virtual time. The computed minima are returned to the initiating process, which then computes the GVT as the minimum of the reported minima. The authors observed the transient message problem which arises from the inability to directly access in transit messages in the system. In the proposed solution to the transient message problem, a sequence number is appended to every message sent from processor p to processor q for all processors p in the set of processors making up the virtual time system. As taught in the Lin et al article, every receiving processor maintains for each sending processor from which it receives messages, the sequence number of some last received message (hereinafter the "Last Received Sequence Number"). Then, when a receiving processor detects the START message, it sends to each sending processor from which it has received messages since the last GVT calculation, a message identifying itself, giving its LVT, and giving the Last Received Sequence Number for that sending processor. Every sending processor thus is able to identify messages which it has sent that are in transit when GVT is calculated and to account for those in transit messages when determining its own local minimum. Manifestly, this algorithm presupposes the maintenance of a respective number sequence for every sending/receiving processor pair.
A general object of the present invention is to improve a virtual time system that utilizes sequence numbers.
Another object of this invention is to provide sequence number control in a virtual time system.
A further objective of this invention is to provide each message between any part of processors in a virtual time system with a unique sequence number.